package arbres;

import listes.*;

public class ArbreDC<E> implements Arbre<E> {
	// Un arbre ArbreDC<E> a une racine et d'éventuels fils stockés dand une liste.
	// Chaque fils a la référence de son père (double chainage).
	// ATTENTION : un arbre peut être un sous-arbre d'un autre arbre, auquel cas il a un (unique) père
	// NE PAS CONFONDRE : racine de l'arbre et racine du plus grand arbre dont il est le sous-arbre

	protected ArbreDC<E> father;
	protected Liste<ArbreDC<E>> children;
	protected E value;

	public ArbreDC(E e) { // arbre réduit à une racine (c'est également une feuille !)
		father = null;
		children = new ListeDC<ArbreDC<E>>();
		value = e;
	}

	private static String seqChar(char c, int i) {
		String res = "";
		for ( ; i>0; i--) res += c;
		return res;
	}

	private static <F> Liste<String> niveaux(Arbre<F> a) {
		String etiq = a.getVal().toString();
		if (a.isLeaf()) return new ListeDC<String>(etiq);
		Liste<String> res = niveaux(a.children().get(0));
		String traits = (a.children().size() == 1 ? "|" : "+");
		int largeurTrait = res.get(0).length();
		for (int i = 1; i < a.children().size(); i++) {
			int largeur1 = res.get(0).length();
			Liste<String> afusionner = niveaux(a.children().get(i));
			int largeur2 = afusionner.get(0).length();
			traits += seqChar('-', largeurTrait) + "+";
			for (int k = 0; k < res.size() && k < afusionner.size(); k++)
				res.set(k, res.get(k) + " " + afusionner.get(k));
			for (int k = res.size(); k < afusionner.size(); k++)
				res.add(k, seqChar(' ', largeur1 + 1) + afusionner.get(k));
			for (int k = afusionner.size(); k < res.size(); k++)
				res.set(k, res.get(k) + seqChar(' ', largeur2 + 1));
			largeurTrait = largeur2;
		}
		traits += seqChar(' ', res.get(res.size() - 1).length()-traits.length());
		res.add(0, traits).add(0, etiq+seqChar(' ', res.get(res.size()-1).length()-etiq.length()));
		return res;
	}

	public String toString() {
		Liste<String> niveaux = niveaux(this);
		String res = "";
		for (int i = 0; i < niveaux.size(); i++)
			res += niveaux.get(i) + "\n";
		return res;
	}

	public E getVal() {	// renvoie la valeur de la RACINE de l'arbre
		return value;
	}

	public E setVal(E e) {// met à jour la valeur de la racine de l'arbre et renvoie la valeur précédente
		E bak = value;
		value = e;
		return bak;
	}

	public boolean isLeaf() { // renvoie vrai si l'arbre est une feuille (racine sans enfants)
		return children.size()==0;
	}

	public int familySize() { // renvoie le nombre de DESCENDANTS depuis la RACINE (racine exclue)
		int res = children.size();
		for (int i = 0; i < children.size(); i++)
			res += children.get(i).familySize();
		return res;
	}

	public int height() { // renvoie la hauteur de l'arbre, à partir de la RACINE
		int max = 0;
		for (int i = 0; i < children.size(); i++) {
			int candidat = children.get(i).height() + 1;
			if (candidat > max) max = candidat;
		}
		return max;
	}

	public Arbre<E> father() { // renvoie le père de l'arbre ou null s'il n'existe pas.
		return father;
	}

	public Arbre<E> ancestor() { // renvoie le premier ancêtre de l'arbre
	// (la racine du plus grand arbre englobant) ou null s'il n'existe pas.
		if (father == null) return null;
		ArbreDC<E> aieul = father;
		for ( ; aieul.father!=null; aieul=aieul.father) {}
		return aieul;
		
		// // Version récursive :
		// if(father==null) return null;
		// if(father.father==null) return father;
		// return father.ancestor();
		 
		// // Version moins élégante :
		// Liste<Arbre<E>> ancestors = ancestors();
		// if(ancestors.size()==0) return null;
		// return ancestors.get(0);
		 
	}

	public Liste<? extends Arbre<E>> children() { // renvoie la liste des enfants de la racine.
		return children;
	}

	public Liste<? extends Arbre<E>> ancestors() { // renvoie la liste des aieux de l'arbre
	// (dans l'ordre depuis le premier ancêtre).
		Liste<Arbre<E>> res = new ListeDC<Arbre<E>>();
		for (ArbreDC<E> aieul=father; aieul!=null; aieul=aieul.father) res.add(0, aieul);
		return res;
		
		// // Version récursive : ATTENTION : rajouter :
		//   // @SuppressWarnings("unchecked") (sans risque : on caste sur le type le plus général)
		// if(father==null) return new ListeDC<Arbre<E>>();
		// return ((Liste<Arbre<E>>)father.ancestors()).add(father);
		
	}

	public Liste<? extends Arbre<E>> brothers() { // renvoie la liste des frères de l'arbre.
		Liste<Arbre<E>> res = new ListeDC<Arbre<E>>();
		if (father != null)
			for (int i = 0; i < father.children.size(); i++) {
				Arbre<E> candidat = father.children.get(i);
				if (this!=candidat) res.add(candidat);
			}
		return res;
	}

	public Liste<? extends Arbre<E>> gen(int n) { // renvoie la liste des déscendants de la racine à la n^ème génération.
		// génération 1 : enfants ; génération 2 : petits enfants ; ...
		// quand l'indice ne correspond pas à une génération possible ou existante, la liste est vide.
		// ou l'instance courante elle-même
		if (n == 1) return children;
		Liste<Arbre<E>> res = new ListeDC<Arbre<E>>();
		if (n < 1) return res;
		for (int i=0; i<children.size(); i++) res.addAll(children.get(i).gen(n - 1));
		return res;
	}

	public boolean contains(Arbre<E> a) { // renvoie vrai si a est un sous-arbre de l'instance courante,
	// ou l'instance courante elle-même
		if (a == this) return true;
		for (int i = 0; i < children.size(); i++)
			if (children.get(i).contains(a)) return true;
		return false;
	}

	public Liste<? extends Arbre<E>> cutAll() { // supprime tous les enfants ; renvoie les orphelins (mis à jours !)
		Liste<Arbre<E>> res = new ListeDC<Arbre<E>>();
		while (children.size() != 0) res.add(cutChild(0));
		return res;
	}

	public Arbre<E> cutChild(int i) throws IndexOutOfBoundsException {
		// renvoie ET SUPPRIME le fils n°i (à partir du fils n°0 le plus à gauche)
		if (i < 0 || i >= children.size()) throw new IndexOutOfBoundsException();
		ArbreDC<E> res = children.remove(i);
		res.father = null;
		return res;
	}

	public ArbreDC<E> getChild(int i) throws IndexOutOfBoundsException {
		// renvoie le fils n°i (à partir du fils n°0 le plus à gauche)
		if (i < 0 || i >= children.size()) throw new IndexOutOfBoundsException();
		return children.get(i);
	}

	public Arbre<E> addChild(Arbre<E> a) throws NullPointerException,
			ArbreCyclique, GreffeDeSousArbre, SousArbreIncoherent {
		// rajoute un fils à la racine A DROITE des éventuels fils déjà existants ;
		// renvoie l'instance courante ;
		// ATTENTION :
		//   1) a doit exister (sinon : NullPointerException)
		//   2) a ne doit pas avoir de père (sinon : GreffeDeSousArbre)
		//   3) a ne doit pas contenir l'instance courante (sinon : ArbreCyclique)
		//   4) a doit être implémenté comme l'instance courante (sinon : SousArbreIncoherent)
		return addChild(children.size(), a);
	}
	
	public Arbre<E> addChild(int i, Arbre<E> a) throws NullPointerException,
			IndexOutOfBoundsException, ArbreCyclique, GreffeDeSousArbre, SousArbreIncoherent {
		// rajoute un fils n°i et déclale les fils existants vers la droite ;
		// (i est compris entre 0 et children() inclu, auquel cas l'arbre est rajouté à la fin) ;
		// renvoie l'instance courante ;
		// ATTENTION :
		//   1) a doit exister (sinon : NullPointerException)
		//   2) a ne doit pas avoir de père (sinon : GreffeDeSousArbre)
		//   3) a ne doit pas contenir l'instance courante (sinon : ArbreCyclique)
		//   4) a doit être implémenté comme l'instance courante (sinon : SousArbreIncoherent)
		//   5) i doit être un indice possible (sinon : IndexOutOfBoundsException)
		if (a == null) throw new NullPointerException();
		if (i < 0 || i > children.size()) throw new IndexOutOfBoundsException();
		ArbreDC<E> al;
		try { al = (ArbreDC<E>) a; }
		catch(ClassCastException e) { throw new SousArbreIncoherent(); }
		if (al.father != null) throw new GreffeDeSousArbre();
		if (al.contains(this)) throw new ArbreCyclique();
		al.father = this;
		children.add(i, al);
		return this;
	}

	public Liste<E> prefixe() { // renvoie la liste des éléments stockés dans l'arbre
	// dans l'ordre correspondant à son parcours préfixe
		Liste<E> res = new ListeDC<E>().add(value);
		for (int i = 0; i < children.size(); i++) res.addAll(children.get(i).prefixe());
		return res;
	}

	public Liste<E> postfixe() { // renvoie la liste des éléments stockés dans l'arbre
	// dans l'ordre correspondant à son parcours postfixe
		Liste<E> res = new ListeDC<E>();
		for (int i = 0; i < children.size(); i++) res.addAll(children.get(i).postfixe());
		return res.add(value);
	}

	public Liste<E> largeur() { // renvoie la liste des éléments stockés dans l'arbre
		// niveau par niveau à partir de la racine
		Liste<E> res = new ListeDC<E>().add(value);
		int height = height();
		for (int n = 1; n <= height; n++) {
			Liste<? extends Arbre<E>> niveaux = gen(n);
			for (int i = 0; i < niveaux.size(); i++) res.add(niveaux.get(i).getVal());
		}
		return res;
	}

	public static void main(String[] args) throws Exception {
		Arbre<Integer> a7 = new ArbreDC<Integer>(7);
		Arbre<Integer> a8 = new ArbreDC<Integer>(8);
		Arbre<Integer> a10 = new ArbreDC<Integer>(10);
		Arbre<Integer> a11 = new ArbreDC<Integer>(11);
		Arbre<Integer> a12 = new ArbreDC<Integer>(12);
		Arbre<Integer> a5 = new ArbreDC<Integer>(5);
		Arbre<Integer> a2 = new ArbreDC<Integer>(2);
		Arbre<Integer> a3 = new ArbreDC<Integer>(3);
		Arbre<Integer> a4 = new ArbreDC<Integer>(4);
		Arbre<Integer> a9 = new ArbreDC<Integer>(9);
		a9.addChild(a10).addChild(a11).addChild(a12);
		a4.addChild(a8).addChild(a9);
		a3.addChild(a7);
		a2.addChild(a3).addChild(a4).addChild(a5);
		System.out.println(a2);
		System.out.println("Valeur de la racine 8 : " + a8.getVal());
		System.out.println("Mise à jour 8->120565 (ancienne valeur : "
				+ a8.setVal(120565) + ")");
		System.out.println("Mise à jour 7->99 (ancienne valeur : "
				+ a7.setVal(99) + ")");
		System.out.println("Arbre à jour :\n" + a2);
		System.out.println("Nombre de descendants de 2 : " + a2.familySize()
				+ " ; hauteur de 2 : " + a2.height());
		System.out.println("Nombre de descendants de 4 : " + a4.familySize()
				+ " ; hauteur de 4 : " + a4.height());
		System.out.println("Nombre de descendants de 12 : " + a12.familySize()
				+ " ; hauteur de 12 : " + a12.height());
		System.out.println("Père de 9 : \n" + a9.father());
		System.out.println("Père de 2 : \n" + a2.father());

		Arbre<Integer> a39 = new ArbreDC<Integer>(39);
		Arbre<Integer> a41 = new ArbreDC<Integer>(41);
		a39.addChild(a41);
		System.out.println("Arbre 2 :\n" + a2);
		System.out.println("Arbre 9 :\n" + a9);
		System.out.println("Arbre 39 :\n" + a39);
		a3.addChild(a39);
		System.out.println("Arbre 2 :\n" + a2);
		System.out.println("Père de 39 :\n"+ a39.father());
		System.out.println("*** Changement de place pour 9 ***");
		a7.addChild(a4.cutChild(1));
		System.out.println("Arbre 2 :\n" + a2);
		System.out.println("*** Changement de place pour 3 ***");
		a4.addChild(1, a2.cutChild(0));
		System.out.println("Arbre 2 :\n" + a2);

		System.out.println("#### ARBRE DE REFERENCE :\n" + a2);
		System.out.println("#### Ancêtres de 9 :\n" + a9.ancestors());
		System.out.println("#### Premier ancêtre de 9 :\n" + a9.ancestor());
		System.out.println("#### FRERES DE 11 :\n" + a11.brothers());
		System.out.println("#### FRERES DE 9 :\n" + a9.brothers());
		System.out.println("#### FRERES DE 39 :\n" + a39.brothers());
		System.out.println("#### FRERES DE 3 :\n" + a3.brothers());
		System.out.println("#### FRERES DE 2 :\n" + a2.brothers());

		System.out.println("#### ARBRE DE REFERENCE :\n" + a2);
		System.out.println("#### Génération 0 :\n" + a2.gen(0));
		System.out.println("#### Génération 1 :\n" + a2.gen(1));
		System.out.println("#### Génération 2 :\n" + a2.gen(2));
		System.out.println("#### Génération 3 :\n" + a2.gen(3));
		System.out.println("#### Génération 4 :\n" + a2.gen(4));

		System.out.println("#### ARBRE DE REFERENCE :\n" + a2);
		System.out.println("Parcours préfixe de l'arbre 2     : " + a2.prefixe());
		System.out.println("Parcours postfixe de l'arbre 2    : " + a2.postfixe());
		System.out.println("Parcours par niveaux de l'arbre 2 : " + a2.largeur());

		System.out.println("**** valeur du père de 3  : "+ a3.father().getVal());
		System.out.println("**** valeur du père de 4  : "+ a4.father().getVal());
		System.out.println("**** valeur du père de 39 : "+ a39.father().getVal());
		System.out.println("**** valeur du père de 5  : "+ a5.father().getVal());
		System.out.println("*** Découpage des enfants de 2 ***");
		a2.cutAll();
		System.out.println("Arbre 2 :\n" + a2);
		System.out.println("**** père de 3  : " + a3.father());
		System.out.println("**** père de 4  : " + a4.father());
		System.out.println("**** père de 39 : " + a39.father());
		System.out.println("**** père de 5  : " + a5.father());
		/*
		 2             
		+-+----------+
		3 4          5
		| +-+         
		7 8 9         
		    +--+--+   
		    10 11 12  
		
		Valeur de la racine 8 : 8
		Mise à jour 8->120565 (ancienne valeur : 8)
		Mise à jour 7->99 (ancienne valeur : 7)
		Arbre à jour :
		2                   
		+--+---------------+
		3  4               5
		|  +------+         
		99 120565 9         
		          +--+--+   
		          10 11 12  
		
		Nombre de descendants de 2 : 9 ; hauteur de 2 : 3
		Nombre de descendants de 4 : 5 ; hauteur de 4 : 2
		Nombre de descendants de 12 : 0 ; hauteur de 12 : 0
		Père de 9 : 
		4              
		+------+       
		120565 9       
		       +--+--+ 
		       10 11 12
		
		Père de 2 : 
		null
		Arbre 2 :
		2                   
		+--+---------------+
		3  4               5
		|  +------+         
		99 120565 9         
		          +--+--+   
		          10 11 12  
		
		Arbre 9 :
		9       
		+--+--+ 
		10 11 12
		
		Arbre 39 :
		39
		| 
		41
		
		Arbre 2 :
		2                      
		+-----+---------------+
		3     4               5
		+--+  +------+         
		99 39 120565 9         
		   |         +--+--+   
		   41        10 11 12  
		
		Père de 39 :
		3    
		+--+ 
		99 39
		   | 
		   41
		
		*** Changement de place pour 9 ***
		Arbre 2 :
		2                   
		+-----------+------+
		3           4      5
		+--------+  |       
		99       39 120565  
		|        |          
		9        41         
		+--+--+             
		10 11 12            
		
		*** Changement de place pour 3 ***
		Arbre 2 :
		2                   
		+------------------+
		4                  5
		+------+            
		120565 3            
		       +--------+   
		       99       39  
		       |        |   
		       9        41  
		       +--+--+      
		       10 11 12     
		
		#### ARBRE DE REFERENCE :
		2                   
		+------------------+
		4                  5
		+------+            
		120565 3            
		       +--------+   
		       99       39  
		       |        |   
		       9        41  
		       +--+--+      
		       10 11 12     
		
		#### Ancêtres de 9 :
		( 2                   
		+------------------+
		4                  5
		+------+            
		120565 3            
		       +--------+   
		       99       39  
		       |        |   
		       9        41  
		       +--+--+      
		       10 11 12     
		 4                 
		+------+          
		120565 3          
		       +--------+ 
		       99       39
		       |        | 
		       9        41
		       +--+--+    
		       10 11 12   
		 3          
		+--------+ 
		99       39
		|        | 
		9        41
		+--+--+    
		10 11 12   
		 99      
		|       
		9       
		+--+--+ 
		10 11 12
		 )
		#### Premier ancêtre de 9 :
		2                   
		+------------------+
		4                  5
		+------+            
		120565 3            
		       +--------+   
		       99       39  
		       |        |   
		       9        41  
		       +--+--+      
		       10 11 12     
		
		#### FRERES DE 11 :
		( 10
		 12
		 )
		#### FRERES DE 9 :
		( )
		#### FRERES DE 39 :
		( 99      
		|       
		9       
		+--+--+ 
		10 11 12
		 )
		#### FRERES DE 3 :
		( 120565
		 )
		#### FRERES DE 2 :
		( )
		#### ARBRE DE REFERENCE :
		2                   
		+------------------+
		4                  5
		+------+            
		120565 3            
		       +--------+   
		       99       39  
		       |        |   
		       9        41  
		       +--+--+      
		       10 11 12     
		
		#### Génération 0 :
		( )
		#### Génération 1 :
		( 4                 
		+------+          
		120565 3          
		       +--------+ 
		       99       39
		       |        | 
		       9        41
		       +--+--+    
		       10 11 12   
		 5
		 )
		#### Génération 2 :
		( 120565
		 3          
		+--------+ 
		99       39
		|        | 
		9        41
		+--+--+    
		10 11 12   
		 )
		#### Génération 3 :
		( 99      
		|       
		9       
		+--+--+ 
		10 11 12
		 39
		| 
		41
		 )
		#### Génération 4 :
		( 9       
		+--+--+ 
		10 11 12
		 41
		 )
		#### ARBRE DE REFERENCE :
		2                   
		+------------------+
		4                  5
		+------+            
		120565 3            
		       +--------+   
		       99       39  
		       |        |   
		       9        41  
		       +--+--+      
		       10 11 12     
		
		Parcours préfixe de l'arbre 2     : ( 2 4 120565 3 99 9 10 11 12 39 41 5 )
		Parcours postfixe de l'arbre 2    : ( 120565 10 11 12 9 99 41 39 3 4 5 2 )
		Parcours par niveaux de l'arbre 2 : ( 2 4 5 120565 3 99 39 9 41 10 11 12 )
		**** valeur du père de 3  : 4
		**** valeur du père de 4  : 2
		**** valeur du père de 39 : 3
		**** valeur du père de 5  : 2
		*** Découpage des enfants de 2 ***
		Arbre 2 :
		2
		
		**** père de 3  : 4                 
		+------+          
		120565 3          
		       +--------+ 
		       99       39
		       |        | 
		       9        41
		       +--+--+    
		       10 11 12   
		
		**** père de 4  : null
		**** père de 39 : 3          
		+--------+ 
		99       39
		|        | 
		9        41
		+--+--+    
		10 11 12   
		
		**** père de 5  : null
		
		*/
	}
}
